package xkp.lesson2;

public class Test1 {

	public static void main(String[] args) {
		 
		//1、ArrayList的常用用法
		//2、LinkedList的常用用法
		//两者比较接近
		//3、ArrayList的底层结构与LinkedList的底层结构
		//4、ArrayList的扩容原理
		
		//算法的时间复杂度   空间复杂度
		//时间复杂度：主要与算法的执行时间相关
		//空间复杂度：主要与算法执行过程中内存的开销相关
		
		//时间复杂度：冒泡排序、归并排序(快速排序一种)、普通查找、二分查找
		//数组与链表数据的查找
		//冒泡排序  极端情况这个数组目前是从大到小排序，要转成从小到大排序
		int[] arr = {5,9,8,7,6,10,4,3,2,1};
		//第一次需要交换的次数  n-1
		//第二次  n-2次
		//第三次 n-3
		// ...
		//2
		//1 
		//冒泡排序最坏的情况为  (n-1)+(n-2)+(n-3)+....+2+1 = (1+n-1)*(n-1)/2 = 
		//(n*n-n)/2  (n^2-n)/2 一般情况会把系数省略  O(n^2)
		//冒泡排序的时间复杂度O(n^2)
		
		//归并排序的时间复杂度
		//log2(n)*n/2;    归并排序的时间复杂度为O(nlog2(n));
		
		
		//普通查找的时间复杂度
		//从前到后依次对比  n    普通查找时间复杂度:O(n)
		//二分查找时间复杂度   首先二分查找数组一定是有序的
		//二分查找  log2(n)    时间复杂度 O(log2(n))
		
		
		//数组与链表查找的时间复杂度
		//如果按照索引查找 
		//数组按照索引查找的时间复杂度为0   
		//链表(双向)的时间复杂度   
		//首先把索引与长度的二分之一比较 如果索引比二分之一大 则在前半部分 可以通过头部遍历
		//如果比二分之一大 则在后半部分 通过尾部遍历
		//双向链表极端时间复杂度为 n/2   O(n) 
		
	}
}
